#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
@FileName: binary_flip.py
@Version: 1.0
@Date: 2023/7/19 14:15
@Description: 整数二进制编码 反转,  反转的数组为 0,1,2,... n
"""

import math


def flip(n: int):
    """
    递归反转算法， 二进制长度为 n 的数，借助长度为 n-1 的数实现
    :param n: 整数，二进制的编码长度
    :return:
    """
    ilen: int = 1 << max(int(math.ceil(math.log2(n))), 1)
    rev = list(range(ilen))
    for i in range(ilen):
        # 长度为n的二进制码, 提取最后一位
        pt1 = (i & 1) << (ilen - 1)
        # 前 n-1 位对应的数字是 i>>1, 反转码是 rev[i>>1]
        # 反转后的位置从 第二位开始, 所以再 >>1
        pt2 = (rev[i >> 1] >> 1)
        # print(f'origin: {i:0{ilen}b}')
        # print(f'part1 : {pt1:0{ilen}b}')
        # print(f'part2 : {pt2:0{ilen}b}')
        rev[i] = pt1 | pt2
        # print(f'{i} => {rev[i]}')
        # print(f'{i:0b} => {rev[i]:0b}')
        # print()
    return rev


if __name__ == '__main__':
    tmp = flip(7)
